package com.hanxiaozhang.recursion;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈递归〉
 *
 * @author hanxinghua
 * @create 2021/9/8
 * @since 1.0.0
 */
public class Recursion {

    public static void main(String[] args) {

        // 小知识验证
        check_getMax1();

//        int[] array = {1, 3, 4, 33, 80, 90, 3, 44, 3, 77, 9};
//        System.out.println(getMax1(array));


    }


    /**
     * 求数组arr[L ... R]最大值，怎么用递归方法实现。
     *
     * @param arr
     * @return
     */
    public static int getMax2(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    /**
     * 范围求最大
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    private static int process(int[] arr, int L, int R) {
        // arr[L..R]范围上只有一个数，直接返回，base case
        if (L == R) {
            return arr[L];
        }
        // 中点
        int mid = L + ((R - L) >> 1);
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

    /**
     * 求数组arr[L ... R]最大值，怎么用递归方法实现。
     *
     * @param array
     * @return
     */
    public static int getMax1(int[] array) {
        int length = array.length;
        if (length > 2) {
            int mid = array.length >> 2 | 1;
            int maxLeft = getMax1(Arrays.copyOfRange(array, 0, mid));
            int maxRight = getMax1(Arrays.copyOfRange(array, mid, array.length));
            return maxLeft > maxRight ? maxLeft : maxRight;
        } else if (length == 2) {
            return array[0] > array[1] ? array[0] : array[1];
        } else if (length == 1) {
            return array[0];
        } else {
            return -1;
        }
    }

    private static void check_getMax1() {
        int i = 1 >> 2;
        System.out.println(i);
        i = 1 / 2;
        System.out.println(i);
        i = 3 / 2;
        System.out.println(i);
        i = 1 >> 2 | 1;
        System.out.println(i);


        int[] array = {1, 2, 3};
        int[] left = Arrays.copyOfRange(array, 0, 1);
        System.out.println(Arrays.toString(left));
        int[] right = Arrays.copyOfRange(array, 1, array.length - 1);
        System.out.println(Arrays.toString(right));
        right = Arrays.copyOfRange(array, 1, array.length);
        System.out.println(Arrays.toString(right));
    }

}
